package pack3;

import pack3.utils.Utils;

import java.util.Arrays;

public class QuikeSort {
    public static void main(String[] args) {
        int []arr=new int[]{7,5,6,9,10,1,3,7,4,3,2};
        int[]arr2=new int[]{10,9,8,7,6,5,4,3,2,1};
        quikeSort1(arr);
        quikeSort1(arr2);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr2));


        int []arr3=new int[]{7,5,6,9,10,1,3,7,4,3,2};
        int[]arr4=new int[]{10,9,8,7,6,5,4,3,2,1};
        quikeSort2(arr3);
        quikeSort2(arr4);
        System.out.println(Arrays.toString(arr3));
        System.out.println(Arrays.toString(arr4));
    }



    //=======================================
    public static void quikeSort1(int []arr){
        quike(arr,0, arr.length-1);
    }

    public static void quike(int []arr,int left,int right){
        if(left>=right)return ;
        int poite=getPermission(arr,left,right);//获取分界点
        quike(arr, left, poite-1);
        quike(arr, poite+1, right);
    }

    public static int getPermission(int []arr,int left,int right){
        int l=left;
        while(left<right){
            while (left<right&&arr[right]>=arr[l]){
                right--;
            }
            while(left<right&&arr[left]<=arr[l]){
                left++;
            }
            Utils.swap(arr,left,right);
        }
        Utils.swap(arr,l,right);
        return right;
    }

    //=======================================


    //=======================================
    public static void quikeSort2(int []arr){
        quike2(arr,0, arr.length-1);
    }

    public static void quike2(int []arr,int left,int right){
        if(left>=right)return ;
        int provoit=getPermission2(arr,left,right);
        quike2(arr,left,provoit-1);
        quike2(arr,provoit+1,right);
    }

    private static int getPermission2(int[]arr,int left,int right) {
        int temp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=temp){
                right--;
            }
            arr[left]=arr[right];

            while(left<right&&arr[left]<=temp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[right]=temp;
        return right;
    }
    //=======================================

}
